{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Filling Bookcase Shelves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minHeightShelves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #填充书架"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个数组 <code>books</code> ，其中&nbsp;<code>books[i] = [thickness<sub>i</sub>, height<sub>i</sub>]</code>&nbsp;表示第 <code>i</code> 本书的厚度和高度。你也会得到一个整数 <code>shelfWidth</code> 。</p>\n",
    "\n",
    "<p><strong>按顺序</strong>&nbsp;将这些书摆放到总宽度为 <code>shelfWidth</code> 的书架上。</p>\n",
    "\n",
    "<p>先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 <code>shelfWidth</code> ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。</p>\n",
    "\n",
    "<p>需要注意的是，在上述过程的每个步骤中，<strong>摆放书的顺序与给定图书数组 </strong><code>books</code><strong> 顺序相同</strong>。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。</li>\n",
    "</ul>\n",
    "\n",
    "<p>每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。</p>\n",
    "\n",
    "<p>以这种方式布置书架，返回书架整体可能的最小高度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2019/06/24/shelves.png\" style=\"width: 337px; height: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "3 层书架的高度和为 1 + 3 + 2 = 6 。\n",
    "第 2 本书不必放在第一层书架上。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> books = [[1,3],[2,4],[3,2]], shelfWidth = 6\n",
    "<strong>输出:</strong> 4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= books.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= thickness<sub>i</sub>&nbsp;&lt;= shelfWidth &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= height<sub>i</sub>&nbsp;&lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [filling-bookcase-shelves](https://leetcode.cn/problems/filling-bookcase-shelves/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [filling-bookcase-shelves](https://leetcode.cn/problems/filling-bookcase-shelves/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]]\\n4', '[[1,3],[2,4],[3,2]]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [10000005]*(n+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(n):\n",
    "            W,H = 0,0\n",
    "            j = i\n",
    "            while j >= 0:\n",
    "                W+=books[j][0]\n",
    "                if W > shelfWidth:\n",
    "                    break\n",
    "                H = max(H,books[j][1])\n",
    "                dp[i+1] = min(dp[i+1],dp[j]+H)\n",
    "                j-=1\n",
    "        return dp[n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        # 给定一个数组，将这些数划分成若干子数组，每个子数组的限制：组内厚度不超过shelfWidth，求每个子数组的最大值之和最小\n",
    "        # dp[i]表示前i个，第i个被作为该组最后一个元素的划分的最小最大值之和\n",
    "        n = len(books)\n",
    "        dp = [inf] * (n + 1)\n",
    "        dp[-1] = 0\n",
    "        for i in range(n):\n",
    "            j = i - 1\n",
    "            sum_width = books[i][0]\n",
    "            mx = books[i][1]\n",
    "            while j >= -1 and sum_width <= shelfWidth:\n",
    "                dp[i] = min(dp[i], dp[j] + mx)\n",
    "                sum_width += books[j][0]\n",
    "                mx = max(mx, books[j][1])\n",
    "                j -= 1\n",
    "        # print(dp)\n",
    "        return dp[n - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [1000000] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            tmp_width, j, h = 0, i, 0\n",
    "            while j > 0:\n",
    "                tmp_width += books[j - 1][0]\n",
    "                if tmp_width > shelfWidth:\n",
    "                    break\n",
    "                h = max(h, books[j - 1][1])\n",
    "                dp[i] = min(dp[i], dp[j - 1] + h)\n",
    "                j -= 1\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books, shelfWidth: int) -> int:\n",
    "\n",
    "        dp = [10e9 for i in range(len(books)+1)]\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(len(books)):\n",
    "\n",
    "            width = 0\n",
    "            height = 0\n",
    "            for j in range(i, -1, -1):\n",
    "                width += books[j][0]\n",
    "                height = max(books[j][1], height)\n",
    "                if width > shelfWidth:\n",
    "                    break\n",
    "                dp[i + 1] = min(dp[j] + height, dp[i + 1])\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:\n",
    "        n = len(books)\n",
    "        f = [0] + [inf] * n \n",
    "        for i in range(n):\n",
    "            max_h, left_w = 0, shelf_width\n",
    "            for j in range(i, -1, -1):\n",
    "                left_w -= books[j][0]\n",
    "                if left_w < 0: break\n",
    "                max_h = max(max_h, books[j][1])  \n",
    "                f[i + 1] = min(f[i + 1], f[j] + max_h)\n",
    "        return f[n] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        # 按顺序放置矩形，使得高度最小\n",
    "\n",
    "        # 1. 递归： \n",
    "        # @cache\n",
    "        # def dfs(i: int) -> int: # dfs(i) 放置books[0...i]后最小高度\n",
    "        #     if i < 0: return 0\n",
    "        #     res, max_h, left_w = inf, 0, shelfWidth\n",
    "\n",
    "        #     for j in range(i, -1, -1):\n",
    "        #         left_w -= books[j][0] # 宽度\n",
    "        #         if left_w < 0: break\n",
    "        #         max_h = max(max_h, books[j][1]) # 从j到i的最大高度\n",
    "        #         res = min(res, dfs(j - 1) + max_h)\n",
    "        #     return res \n",
    "        # return dfs(len(books) - 1)\n",
    "\n",
    "        # 2. 迭代\n",
    "        n = len(books)\n",
    "        f = [0] + [inf] * n # 在前面插入一个状态表示dfs(-1) = 0\n",
    "        for i in range(n):\n",
    "            max_h, left_w = 0, shelfWidth\n",
    "            for j in range(i, -1, -1):\n",
    "                left_w -= books[j][0]\n",
    "                if left_w < 0: break\n",
    "                max_h = max(max_h, books[j][1])\n",
    "                f[i + 1] = min(f[i + 1], f[j] + max_h)\n",
    "        return f[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        dp = [0 for i in range(len(books))]\n",
    "        dp[0] = books[0][1]\n",
    "\n",
    "        # 本层以第i本书结尾的最小高度\n",
    "        for i in range(1, len(books)):\n",
    "            max_h = books[i][1]\n",
    "            thick = books[i][0]\n",
    "            dp[i] = books[i][1] + dp[i-1]\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if thick + books[j][0] > shelfWidth:\n",
    "                    break\n",
    "\n",
    "                thick += books[j][0]\n",
    "                max_h = max(max_h, books[j][1])\n",
    "                if j != 0:\n",
    "                    dp[i] = min(dp[i], dp[j-1] + max_h)\n",
    "                else:\n",
    "                    dp[i] = max_h\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n=len(books)\n",
    "        dp=[1000000]*(n+1)\n",
    "        dp[0]=0\n",
    "        dp[1]=books[0][1]\n",
    "        for i in range(1,n):\n",
    "            temp=shelfWidth-books[i][0]\n",
    "            j=i\n",
    "            height=books[i][1]\n",
    "            while temp>=0 and j>=0:\n",
    "                dp[i+1]=min(dp[i+1],dp[j]+height)\n",
    "                height=max(height,books[j-1][1])\n",
    "                temp-=books[j-1][0]\n",
    "                j-=1\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [int(1e9)] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            h,w = 0, 0\n",
    "            for j in range(i,0,-1):\n",
    "                w += books[j-1][0]\n",
    "                if w > shelfWidth:\n",
    "                    break\n",
    "                h = max(h,books[j-1][1])\n",
    "                dp[i] = min(dp[i], dp[j-1]+h)\n",
    "        return dp[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        f = [0] * (n + 1)\n",
    "        for i, (w, h) in enumerate(books):\n",
    "            res = inf\n",
    "            j = i\n",
    "            w = 0\n",
    "            mh = 0\n",
    "            while j >= 0 and w + books[j][0] <= shelfWidth:\n",
    "                w += books[j][0]\n",
    "                mh = max(mh, books[j][1])\n",
    "                res = min(res, f[j] + mh)\n",
    "                j -= 1\n",
    "            f[i + 1] = res\n",
    "        # print(f'f:{f}')\n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        inf = float('inf')\n",
    "        dp = [inf] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for i, b in enumerate(books):\n",
    "            curWidth, maxHeight = 0, 0\n",
    "            j = i\n",
    "            while j >= 0:\n",
    "                curWidth += books[j][0]\n",
    "                if curWidth > shelfWidth:\n",
    "                    break\n",
    "                maxHeight = max(maxHeight, books[j][1])\n",
    "                dp[i + 1] = min(dp[i + 1], dp[j] + maxHeight)\n",
    "                j -= 1\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [0] + [1000*1000 for _ in range(n)]\n",
    "        for i in range(1, n+1):\n",
    "            tw, j, mh = 0, i, 0\n",
    "            while j > 0:\n",
    "                if tw + books[j-1][0] <= shelfWidth:\n",
    "                    tw += books[j-1][0]\n",
    "                    mh = max(mh, books[j-1][1])\n",
    "                    dp[i] = min(dp[i], dp[j-1] + mh)\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    break\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n=len(books)\n",
    "        dp=[0]+[1000000]*n\n",
    "    \n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            tmp_width,j,h=0,i,0\n",
    "            while j>0:\n",
    "                tmp_width+=books[j-1][0]\n",
    "                if tmp_width>shelfWidth:\n",
    "                    break\n",
    "                \n",
    "                h=max(h,books[j-1][1])\n",
    "                dp[i]=min(dp[i],dp[j-1]+h)\n",
    "                j-=1\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n=len(books)\n",
    "        dp=[float(\"inf\")]*(n+1)\n",
    "        dp[0]=0\n",
    "        for i in range(1,n+1):\n",
    "            w,h=books[i-1]\n",
    "            j=i-1\n",
    "            now=0\n",
    "            height=0\n",
    "            while True:\n",
    "                #print(\"ijwh\",i,j,w,h)\n",
    "                if j<0:\n",
    "                    break\n",
    "                w2,h2=books[j]\n",
    "                #print(\"w2h2\",w2,h2)\n",
    "                now+=w2\n",
    "                height=max(height,h2)\n",
    "                #print(now,height)\n",
    "                if now<=shelfWidth:\n",
    "                    #print(\"<<\",i,j)\n",
    "                    dp[i]=min(dp[i],dp[j]+height)\n",
    "                else:\n",
    "                    break\n",
    "                j-=1\n",
    "        #print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        # 书架整体的高度为各层高之和。摆放书的顺序与给定图书数组 books 顺序相同。它们的厚度之和小于等于书架的宽度 shelfWidth\n",
    "        # @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        # def dfs(i: int) -> int:\n",
    "        #     if i < 0: return 0  # 没有书了，高度是 0\n",
    "        #     res, max_h, left_w = inf, 0, shelfWidth\n",
    "        #     for j in range(i, -1, -1):\n",
    "        #         left_w -= books[j][0]\n",
    "        #         if left_w < 0: break  # 空间不足，无法放书\n",
    "        #         max_h = max(max_h, books[j][1])  # 从 j 到 i 的最大高度\n",
    "        #         res = min(res, dfs(j - 1) + max_h)\n",
    "        #     return res\n",
    "        # return dfs(len(books) - 1)\n",
    "\n",
    "        n = len(books)\n",
    "        f = [0]+[inf]*n\n",
    "        for i in range(n):\n",
    "            max_h, left_w = 0, shelfWidth\n",
    "            for j in range(i,-1,-1):\n",
    "                left_w -= books[j][0]\n",
    "                if left_w<0:\n",
    "                    break\n",
    "                max_h = max(max_h,books[j][1])\n",
    "                f[i+1] = min(f[i+1],f[j]+max_h)#f[i+1]再不停更新\n",
    "        return f[-1]\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:\n",
    "        n = len(books)\n",
    "        f = [0] + [inf] * n  # 在前面插入一个状态表示 dfs(-1)=0\n",
    "        for i in range(n):\n",
    "            max_h, left_w = 0, shelf_width\n",
    "            for j in range(i, -1, -1):\n",
    "                left_w -= books[j][0]\n",
    "                if left_w < 0: break  # 空间不足，无法放书\n",
    "                max_h = max(max_h, books[j][1])  # 从 j 到 i 的最大高度\n",
    "                f[i + 1] = min(f[i + 1], f[j] + max_h)\n",
    "        return f[n]  # 翻译自 dfs(n-1)\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/filling-bookcase-shelves/solutions/2240688/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-0vg6/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [inf] * (n + 1)\n",
    "        # print(dp)\n",
    "        dp[0] = 0\n",
    "        for i, b in enumerate(books):\n",
    "            # print(i,b)\n",
    "            curWidth = 0\n",
    "            maxHeight = 0\n",
    "            j = i\n",
    "            while j >= 0:\n",
    "                curWidth += books[j][0]\n",
    "                if curWidth > shelfWidth:\n",
    "                    break\n",
    "                maxHeight = max(maxHeight, books[j][1])\n",
    "                dp[i + 1] = min(dp[i + 1], dp[j] + maxHeight)\n",
    "                j -= 1\n",
    "        return dp[n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        # 动态规划解法\n",
    "        # 当前书是选择放在和上一本书同一层，还是新开一层\n",
    "        # 记忆化搜索来解决当前问题\n",
    "        # dfs(i) 表示前i本书构成的最小高度\n",
    "        # 分组dp\n",
    "        # f[i] = min(f[i-1] + books[i][1], f[i-2] + books[i][1] + books[i-1][1], f[i-3] + books[i-2-][1])\n",
    "        # 需要求一下前缀和\n",
    "        n = len(books)\n",
    "        f = [inf] * (n + 1)\n",
    "        f[0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            # 前缀和优化，优化最大值\n",
    "            s, mx = 0, 0\n",
    "            for j in range(i, 0, -1):\n",
    "                s += books[j-1][0]\n",
    "                mx = max(mx, books[j-1][1])\n",
    "                if s <= shelfWidth:\n",
    "                    f[i] = min(f[i], f[j-1] + mx)\n",
    "                else:\n",
    "                    break\n",
    "        print(f)\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n=len(books)\n",
    "        dp=[sys.maxsize]*(n+1)\n",
    "        dp[0]=0\n",
    "        for i in range(1,n+1):\n",
    "            maxHight=0\n",
    "            j=1\n",
    "            curWidth=0\n",
    "            while i-j>=0:\n",
    "                book=books[i-j]\n",
    "                curWidth+=book[0]\n",
    "                maxHight=max(maxHight,book[1])\n",
    "                if curWidth>shelfWidth:\n",
    "                    break\n",
    "                dp[i]=min(dp[i],dp[i-j]+maxHight)\n",
    "                j+=1\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [inf] * (n + 1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for j in range(n):\n",
    "            w = 0\n",
    "            h = 0\n",
    "            for i in range(j, -1, -1):\n",
    "                w += books[i][0] \n",
    "                if w <= shelfWidth:\n",
    "                    h = max(h, books[i][1])\n",
    "                    dp[j+1] = min(dp[j+1], h + dp[i])\n",
    "                else:\n",
    "                    break\n",
    "        return dp[-1]\n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        dp = [[0, 0] for _ in range(shelfWidth + 1)]\n",
    "        for bookIdx in range(len(books)):\n",
    "            # for eachRemainWid in range(len(shelfWidth), -1, -1):\n",
    "            for eachRemainWid in range(shelfWidth + 1):\n",
    "                if eachRemainWid + books[bookIdx][0] <= shelfWidth:\n",
    "                    totalHeight, lastHeight = dp[eachRemainWid + books[bookIdx][0]]\n",
    "                    update = max(0, books[bookIdx][1] - lastHeight)\n",
    "                    dp[eachRemainWid] = [totalHeight + update, lastHeight + update]  # fitin\n",
    "                else:\n",
    "                    minHeight = min(dp[:eachRemainWid])[0]\n",
    "                    for eachRRemainWid in range(eachRemainWid, shelfWidth + 1):\n",
    "                        dp[eachRRemainWid] = [minHeight, 0]\n",
    "                    break\n",
    "        return min(dp)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [inf] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for i, b in enumerate(books):\n",
    "            curWidth = 0\n",
    "            maxHeight = 0\n",
    "            j = i\n",
    "            while j >= 0:\n",
    "                curWidth += books[j][0]\n",
    "                if curWidth > shelfWidth:\n",
    "                    break\n",
    "                maxHeight = max(maxHeight, books[j][1])\n",
    "                dp[i + 1] = min(dp[i + 1], dp[j] + maxHeight)\n",
    "                j -= 1\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [1000000] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            tmp_width, j, h = 0, i, 0\n",
    "            while j > 0:\n",
    "                tmp_width += books[j - 1][0]\n",
    "                if tmp_width > shelf_width:\n",
    "                    break\n",
    "                h = max(h, books[j - 1][1])\n",
    "                dp[i] = min(dp[i], dp[j - 1] + h)\n",
    "                j -= 1\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [inf] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for i, b in enumerate(books):\n",
    "            curWidth = 0\n",
    "            maxHeight = 0\n",
    "            j = i\n",
    "            while j >= 0:\n",
    "                curWidth += books[j][0]\n",
    "                if curWidth > shelfWidth:\n",
    "                    break\n",
    "                maxHeight = max(maxHeight, books[j][1])\n",
    "                dp[i + 1] = min(dp[i + 1], dp[j] + maxHeight)\n",
    "                j -= 1\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        ans = [0] + [1000000] * n\n",
    "        for i in range(0,n):\n",
    "            w, h = books[i]\n",
    "            j = i\n",
    "            while w <= shelfWidth:\n",
    "                ans[i+1] = min(ans[i+1], ans[j]+h)\n",
    "                if j == 0:\n",
    "                    break\n",
    "                j -= 1\n",
    "                w += books[j][0]\n",
    "                h = max(h, books[j][1])\n",
    "        # print(ans)\n",
    "        return ans[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [0] + [sys.maxsize] * n\n",
    "        for i in range(1, n + 1):\n",
    "            maxVal = 0\n",
    "            curWidth = 0\n",
    "            for j in range(1, min(shelfWidth, i) + 1):\n",
    "                curWidth += books[i - j][0]\n",
    "                if curWidth > shelfWidth:\n",
    "                    break\n",
    "                maxVal = max(maxVal, books[i - j][1])\n",
    "                dp[i] = min(dp[i], dp[i - j] + maxVal)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [inf] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            tmp_width, j, h = 0, i, 0\n",
    "            while j > 0:\n",
    "                tmp_width += books[j - 1][0]\n",
    "                if tmp_width > shelf_width:\n",
    "                    break\n",
    "                h = max(h, books[j - 1][1])\n",
    "                dp[i] = min(dp[i], dp[j - 1] + h)\n",
    "                j -= 1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        dp = [100000000000]*(len(books)+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1,len(books)+1):\n",
    "            cur_len = 0\n",
    "            h = 0\n",
    "            for j in range(i-1,-1,-1):\n",
    "                cur_len+=books[j][0]\n",
    "                if cur_len>shelfWidth:\n",
    "                    break\n",
    "                h = max(h,books[j][1])\n",
    "                dp[i]=min(dp[i],dp[j]+h)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [inf] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for i, b in enumerate(books):\n",
    "            curWidth = 0\n",
    "            maxHeight = 0\n",
    "            j = i\n",
    "            while j >= 0:\n",
    "                curWidth += books[j][0]\n",
    "                if curWidth > shelfWidth:\n",
    "                    break\n",
    "                maxHeight = max(maxHeight, books[j][1])\n",
    "                dp[i + 1] = min(dp[i + 1], dp[j] + maxHeight)\n",
    "                j -= 1\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n=len(books)\n",
    "        dp=[inf]*(n+1)\n",
    "        dp[0]=0\n",
    "        for i in range(1,n+1):\n",
    "            cur=shelfWidth\n",
    "            high=0\n",
    "            for j in range(i-1,-1,-1):\n",
    "                cur-=books[j][0]\n",
    "                if cur<0:\n",
    "                    break\n",
    "                high=max(high,books[j][1])\n",
    "                dp[i]=min(dp[i],dp[j]+high)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        # 递归\n",
    "        # @cache \n",
    "        # def dfs(i:int)-> int:\n",
    "        #     if i < 0: return 0 # 没有书，高度为0\n",
    "        #     res, max_h, left_w = inf, 0, shelfWidth\n",
    "        #     for j in range(i, -1, -1): # 遍历书集合\n",
    "        #         left_w -= books[j][0]\n",
    "        #         if left_w < 0:break #空间不足，无法放书\n",
    "        #         max_h = max(max_h, books[j][1])# 从j到i的最大高度\n",
    "        #         res = min(res, dfs(j - 1) + max_h)\n",
    "        #     return res\n",
    "        # return dfs(len(books) - 1)\n",
    "\n",
    "        n = len(books)\n",
    "        f = [0] + [inf] * n #在前面插入一个状态表示dfs(-1)=0\n",
    "        for i in range(n):\n",
    "            max_h, left_w = 0, shelfWidth\n",
    "            for j in range(i, -1, -1):\n",
    "                left_w -= books[j][0]\n",
    "                if left_w < 0: break # 空间不足，无法放书\n",
    "                max_h = max(max_h, books[j][1]) # 从j到i的最大高度\n",
    "                f[i + 1] = min(f[i +  1], f[j] + max_h)\n",
    "        return f[n]  # 翻译子dfs(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        dp = [10**6] * len(books)\n",
    "        dp[0] = books[0][1]\n",
    "        for i in range(1,len(books)):\n",
    "            c_thick = shelfWidth - books[i][0]\n",
    "            c_hight = books[i][1]\n",
    "            dp[i] = min(dp[i],c_hight + dp[i-1])\n",
    "            j = i - 1\n",
    "            while j >= 0 and c_thick - books[j][0] >= 0:\n",
    "                c_thick -= books[j][0]\n",
    "                c_hight = max(c_hight,books[j][1])\n",
    "                if j-1 >= 0:\n",
    "                    dp[i] = min(dp[i],c_hight+dp[j-1])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i],c_hight)\n",
    "                j -= 1\n",
    "        return dp[len(books)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [1000000] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            tmp_width, j, h = 0, i, 0\n",
    "            while j > 0:\n",
    "                tmp_width += books[j - 1][0]\n",
    "                if tmp_width > shelfWidth:\n",
    "                    break\n",
    "                h = max(h, books[j - 1][1])\n",
    "                dp[i] = min(dp[i], dp[j - 1] + h)\n",
    "                j -= 1\n",
    "\n",
    "        return dp[-1]\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [float('inf')] * (n + 1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            width = 0\n",
    "            max_heigth = 0\n",
    "            j = i\n",
    "            while j:\n",
    "                if width + books[j - 1][0] > shelfWidth:\n",
    "                    break\n",
    "                width += books[j - 1][0]\n",
    "                max_heigth = max(max_heigth, books[j - 1][1])\n",
    "                dp[i] = min(dp[i], dp[j - 1] + max_heigth)\n",
    "                j -= 1\n",
    "                \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def max_(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def min_(a, b):\n",
    "    return a if a < b else b\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [inf]*(n+1)\n",
    "        dp[0] =0\n",
    "        for i in range(n):\n",
    "            w = h = 0\n",
    "            for j in range(i, -1, -1):\n",
    "                ww, hh = books[j]\n",
    "                if w + ww > shelfWidth:\n",
    "                    break\n",
    "                w += ww\n",
    "                h = max_(h, hh)\n",
    "                dp[i+1] = min_(dp[i+1], dp[j] + h)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            th, height = books[i-1]\n",
    "            dp[i] = dp[i-1] + height\n",
    "            cur_th = th\n",
    "            j = i\n",
    "            max_h = height\n",
    "            while j-1>=1 and books[j-2][0]+cur_th<=shelfWidth:\n",
    "                j -= 1\n",
    "                cur_th += books[j-1][0]\n",
    "                max_h = max(max_h, books[j-1][1])\n",
    "                dp[i] = min(dp[i], max_h+dp[j-1])\n",
    "            pass\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        # dp[i]表示前i本书的最小高度\n",
    "        # 第i本书，要么重新放新的一层，要么和之前的书放一起。（厚度不超过书架宽度）\n",
    "        n = len(books)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            th, height = books[i-1]\n",
    "            dp[i] = dp[i-1] + height\n",
    "            cur_th = th\n",
    "            j = i\n",
    "            max_h = height\n",
    "            while j-1>=1 and books[j-2][0]+cur_th<=shelfWidth:\n",
    "                j -= 1\n",
    "                cur_th += books[j-1][0]\n",
    "                max_h = max(max_h, books[j-1][1])\n",
    "                dp[i] = min(dp[i], max_h+dp[j-1])\n",
    "            pass\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [math.inf] * n\n",
    "        for i in range(n):\n",
    "            h = 0\n",
    "            w = 0\n",
    "            for j in range(i, -1, -1):\n",
    "                w += books[j][0]\n",
    "                h = max(books[j][1], h)\n",
    "                if w > shelfWidth:\n",
    "                    break\n",
    "                if j > 0:\n",
    "                    dp[i] = min(dp[i], h + dp[j - 1])\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], h)\n",
    "        return dp[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    dp[i]表示前i本书放置的最小高度，每次遍历第i本书的时候先假设第i本书先单独放一个架子，然后依次\n",
    "    向前取书，每取一本前面的书计算一下此事这种方法推导出的dp[i]是不是更优的，直到第i本书的那一行\n",
    "    已经放满了\n",
    "    '''\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        '''\n",
    "        这里长度设置成n + 1是因为有向前遍历的过程，很有可能所有的书都能放在一行中，此时累加的\n",
    "        dp[0]其实是一个值为0的初始值，所以得留一个在最前面\n",
    "        '''\n",
    "        dp = [float('inf')] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        '''\n",
    "        按照dp的维度开始遍历\n",
    "        '''\n",
    "        for i in range(1, n + 1):\n",
    "            '''\n",
    "            和第i本书放在同一行书累加的宽度\n",
    "            '''\n",
    "            width = 0\n",
    "            '''\n",
    "            和第i本书放在同一行书里面最高的那本\n",
    "            '''\n",
    "            max_height = 0\n",
    "            '''\n",
    "            初始j就是i，表示先把第i本书单独放一行\n",
    "            '''\n",
    "            j = i\n",
    "            while j:\n",
    "                if width + books[j - 1][0] > shelfWidth:\n",
    "                    break\n",
    "                width += books[j - 1][0]\n",
    "                max_height = max(max_height, books[j - 1][1])\n",
    "                '''\n",
    "                随着j的向前移动，dp[j - 1]表示和第i本书没有放在同一行的书需要的最小高度\n",
    "                '''\n",
    "                dp[i] = min(dp[i], dp[j - 1] + max_height)\n",
    "                j -= 1\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [float('inf')] * n \n",
    "        dp[0] = books[0][1]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            w = 0\n",
    "            mx = 0\n",
    "            for j in range(i, -1, -1):\n",
    "                if w + books[j][0] <= shelfWidth:\n",
    "                    mx = max(mx, books[j][1])\n",
    "                    w += books[j][0]\n",
    "                    if j > 0:\n",
    "                        dp[i] = min(dp[i], dp[j-1] + mx) \n",
    "                    else:\n",
    "                        dp[i] = min(dp[i], mx) \n",
    "                else:\n",
    "                    break \n",
    "        #print(dp) \n",
    "        return dp[n-1] \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [0]+[inf]*n\n",
    "        for i, b in enumerate(books):\n",
    "            width = shelfWidth\n",
    "            maxheight = 0\n",
    "            j = i \n",
    "            while j >= 0:\n",
    "                width -= books[j][0]\n",
    "                if width < 0:\n",
    "                    break\n",
    "                maxheight = max(maxheight, books[j][1])\n",
    "                dp[i+1] = min(dp[i+1], dp[j]+maxheight)\n",
    "                j -= 1\n",
    "        return dp[-1]\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [0] + [1000*1000 for _ in range(n)]\n",
    "        for i in range(1, n+1):\n",
    "            tmp_w, j, h = 0, i, 0\n",
    "            while j > 0:\n",
    "                tmp_w += books[j-1][0]\n",
    "                if tmp_w > shelfWidth:\n",
    "                    break\n",
    "                h = max(h, books[j-1][1])\n",
    "                dp[i] = min(dp[i], dp[j-1]+h)\n",
    "                j -= 1\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:\n",
    "        n = len(books)\n",
    "        f = [0] + [inf] * n  # 在前面插入一个状态表示 dfs(-1)=0\n",
    "        for i in range(n):\n",
    "            max_h, left_w = 0, shelf_width\n",
    "            for j in range(i, -1, -1):\n",
    "                left_w -= books[j][0]\n",
    "                if left_w < 0: break  # 空间不足，无法放书\n",
    "                max_h = max(max_h, books[j][1])  # 从 j 到 i 的最大高度\n",
    "                f[i + 1] = min(f[i + 1], f[j] + max_h)\n",
    "        return f[n]  # 翻译自 dfs(n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [float(\"inf\")] * (n + 1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i, book in enumerate(books):\n",
    "            width = height = 0\n",
    "            for j in range(i, -1, -1):\n",
    "                w, h = books[j]\n",
    "                width += w\n",
    "                if width > shelfWidth:\n",
    "                    break\n",
    "\n",
    "                height = max(height, h)\n",
    "                dp[i + 1] = min(dp[i + 1], dp[j] + height)\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [float('inf')]*(n+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(n):\n",
    "            tmp = 0\n",
    "            maxh = 0\n",
    "            for j in range(i,-1,-1):\n",
    "                if(tmp + books[j][0] > shelfWidth):\n",
    "                    break\n",
    "                maxh = max(maxh, books[j][1])\n",
    "                tmp += books[j][0]\n",
    "                dp[i+1] = min(dp[i+1], dp[j] + maxh)\n",
    "        return dp[n]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        # dp[i] 表示前i本书的最小高度\n",
    "        dp = [float('inf')] * (n + 1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i, b in enumerate(books):\n",
    "            curWidth = 0\n",
    "            maxHeight = 0\n",
    "            j = i\n",
    "            while j >= 0:\n",
    "                curWidth += books[j][0]\n",
    "                if curWidth > shelfWidth:\n",
    "                    break\n",
    "\n",
    "                maxHeight = max(maxHeight, books[j][1])\n",
    "                dp[i+1] = min(dp[i+1], dp[j] + maxHeight)\n",
    "                j -= 1\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [float('inf')]*(n+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(n):\n",
    "            tmp = 0\n",
    "            maxh = 0\n",
    "            for j in range(i,-1,-1):\n",
    "                if(tmp + books[j][0] > shelfWidth):\n",
    "                    break\n",
    "                maxh = max(maxh, books[j][1])\n",
    "                tmp += books[j][0]\n",
    "                dp[i+1] = min(dp[i+1], dp[j] + maxh)\n",
    "        return dp[n]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [float('inf')]*(n+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(n):\n",
    "            tmp = 0\n",
    "            maxh = 0\n",
    "            for j in range(i,-1,-1):\n",
    "                if(tmp + books[j][0] > shelfWidth):\n",
    "                    break\n",
    "                maxh = max(maxh, books[j][1])\n",
    "                tmp += books[j][0]\n",
    "                dp[i+1] = min(dp[i+1], dp[j] + maxh)\n",
    "        return dp[n]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "\n",
    "        n = len(books)\n",
    "        dp = [1000000] * (n + 1)\n",
    "        dp[0] = 0 \n",
    "\n",
    "        for i, b in enumerate(books):\n",
    "            curWidth = 0\n",
    "            maxHeight = 0\n",
    "            j = i\n",
    "            while j >= 0:\n",
    "                curWidth += books[j][0]\n",
    "                if curWidth > shelfWidth:\n",
    "                    break\n",
    "                maxHeight = max(maxHeight, books[j][1])\n",
    "                dp[i + 1] = min(dp[i + 1], dp[j] + maxHeight)\n",
    "                j -= 1\n",
    "        return dp[n]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [float('inf')] * (n + 1) # 以i结尾所能形成的最小高度\n",
    "        dp[0] = 0\n",
    "        dp[1] = books[0][1]\n",
    "        for i in range(2, n + 1):\n",
    "            totalWidth = 0\n",
    "            maxHeight = 0\n",
    "            for j in range(i, 0, -1):\n",
    "                totalWidth += books[j - 1][0]\n",
    "                if totalWidth > shelfWidth:\n",
    "                    break\n",
    "                maxHeight = max(maxHeight, books[j - 1][1])\n",
    "                dp[i] = min(dp[i], dp[j - 1] + maxHeight) # 最后一层的高度加上之前所有层的高度\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [float('inf')]*(n+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(n):\n",
    "            tmp = 0\n",
    "            maxh = 0\n",
    "            for j in range(i,-1,-1):\n",
    "                if(tmp + books[j][0] > shelfWidth):\n",
    "                    break\n",
    "                maxh = max(maxh, books[j][1])\n",
    "                tmp += books[j][0]\n",
    "                dp[i+1] = min(dp[i+1], dp[j] + maxh)\n",
    "        return dp[n]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            cur_w = books[i][0]\n",
    "            cur_h = books[i][1]\n",
    "            dp[i] = cur_h\n",
    "            if i > 0:\n",
    "                dp[i] += dp[i-1]\n",
    "            p = i - 1\n",
    "            while p >= 0 and cur_w + books[p][0] <= shelfWidth:\n",
    "                cur_w += books[p][0]\n",
    "                cur_h = max(cur_h, books[p][1])\n",
    "                if p == 0:\n",
    "                    dp[i] = min(dp[i], cur_h)\n",
    "                else:\n",
    "                    dp[i] = min(dp[i], cur_h + dp[p-1])\n",
    "                p -= 1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [1000000] * (n + 1)\n",
    "        dp[0] = 0 \n",
    "\n",
    "        for i, b in enumerate(books):\n",
    "            curWidth = 0\n",
    "            maxHeight = 0\n",
    "            j = i\n",
    "            while j >= 0:\n",
    "                curWidth += books[j][0]\n",
    "                if curWidth > shelfWidth:\n",
    "                    break\n",
    "                maxHeight = max(maxHeight, books[j][1])\n",
    "                dp[i + 1] = min(dp[i + 1], dp[j] + maxHeight)\n",
    "                j -= 1\n",
    "        return dp[n]    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [1000000 for _ in range(n+1)]\n",
    "        dp[0] = 0\n",
    "        width = 0\n",
    "        h = 0\n",
    "        for i in range(1, n+1):\n",
    "            width = 0\n",
    "            h = 0\n",
    "            for j in range(i,0,-1):\n",
    "                width += books[j-1][0]\n",
    "                if width > shelfWidth:\n",
    "                    break\n",
    "                h = max(h, books[j-1][1])\n",
    "                dp[i] = min(dp[i],dp[j-1]+h)\n",
    "                j -= 1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        dp = [1000000] * (len(books)+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, len(dp)):\n",
    "            width = 0\n",
    "            height = 0\n",
    "            j = i\n",
    "            while j > 0:\n",
    "                width += books[j-1][0]\n",
    "                if width > shelfWidth:\n",
    "                    break\n",
    "                height = max(height, books[j - 1][1])\n",
    "                dp[i] = min(dp[i], dp[j-1]+height)\n",
    "                j -= 1\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [1000000 for _ in range(n+1)]\n",
    "        dp[0] = 0\n",
    "        width = 0\n",
    "        h = 0\n",
    "        for i in range(1, n+1):\n",
    "            width = 0\n",
    "            h = 0\n",
    "            for j in range(i,0,-1):\n",
    "                width += books[j-1][0]\n",
    "                if width > shelfWidth:\n",
    "                    break\n",
    "                h = max(h, books[j-1][1])\n",
    "                dp[i] = min(dp[i],dp[j-1]+h)\n",
    "                j -= 1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + books[i][0]            \n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            dp[i+1] = dp[i] + books[i][1]\n",
    "            ceil = books[i][1]\n",
    "            for j in range(i-1, -1, -1):\n",
    "                ceil = ceil if ceil > books[j][1] else books[j][1]\n",
    "                if pre[i+1] - pre[j] <= shelfWidth:\n",
    "                    dp[i+1] = dp[i+1] if dp[i+1] < dp[j] + ceil else dp[j] + ceil\n",
    "                else:\n",
    "                    break\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n = len(books)\n",
    "        dp = [float('inf')] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = books[0][1]\n",
    "        for i in range(2, n + 1):\n",
    "            totalWidth = 0\n",
    "            maxHeight = 0\n",
    "            for j in range(i, 0, -1):\n",
    "                totalWidth += books[j - 1][0]\n",
    "                if totalWidth > shelfWidth:\n",
    "                    break\n",
    "                maxHeight = max(maxHeight, books[j - 1][1])\n",
    "                dp[i] = min(dp[i], dp[j - 1] + maxHeight)\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n=len(books)\n",
    "        dp=[float(\"inf\")]*(n+1)\n",
    "        dp[0]=0\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            j=i\n",
    "            h=0\n",
    "            maxwidth=0\n",
    "            while j>0:\n",
    "                maxwidth+=books[j-1][0]\n",
    "                if maxwidth>shelfWidth:\n",
    "                    break\n",
    "                h=max(h,books[j-1][1])\n",
    "                dp[i]=min(dp[i],dp[j-1]+h)\n",
    "                j=j-1\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n=len(books)\n",
    "        dp=[float(\"inf\")]*(n+1)\n",
    "        dp[0]=0\n",
    "        dp[1]=books[0][1]\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            h=books[i-1][1]\n",
    "            t=books[i-1][0]\n",
    "            tmp=shelfWidth-t\n",
    "            dp[i]=dp[i-1]+h\n",
    "            for j in range(i-1,0,-1):\n",
    "                if tmp-books[j-1][0]>=0:\n",
    "                    h=max(h,books[j-1][1])\n",
    "                   # if i==4:\n",
    "                     #   print(j,h,tmp)\n",
    "                    dp[i]=min(dp[i],dp[j-1]+h)\n",
    "                    tmp=tmp-books[j-1][0]\n",
    "                else:\n",
    "                    break\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n=len(books)\n",
    "        dp=[float(\"inf\")]*(n+1)\n",
    "        dp[0]=0\n",
    "        for i in range(1,n+1):\n",
    "            w,h=books[i-1]\n",
    "            j=i-1\n",
    "            now=0\n",
    "            height=0\n",
    "            while True:\n",
    "                print(\"ijwh\",i,j,w,h)\n",
    "                if j<0:\n",
    "                    break\n",
    "                w2,h2=books[j]\n",
    "                print(\"w2h2\",w2,h2)\n",
    "                now+=w2\n",
    "                height=max(height,h2)\n",
    "                print(now,height)\n",
    "                if now<=shelfWidth:\n",
    "                    print(\"<<\",i,j)\n",
    "                    dp[i]=min(dp[i],dp[j]+height)\n",
    "                else:\n",
    "                    break\n",
    "                j-=1\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i < 0:return 0\n",
    "            res, max_h, left_w = inf, 0, shelfWidth\n",
    "            for j in range(i, -1, -1):\n",
    "                left_w-=books[j][0]\n",
    "                if left_w < 0:break\n",
    "                max_h = max(max_h, books[j][1]) # 从j-i的最大高度\n",
    "                res = min(res, dfs(j-1)+max_h) # 当前层加上以前j-1de层数\n",
    "            return res\n",
    "        return dfs(len(books) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n=len(books)\n",
    "        @cache\n",
    "        def g(i):\n",
    "           if i==n:\n",
    "               return 0\n",
    "           res,h,r=inf,0,shelfWidth\n",
    "           for j in range(i,n):\n",
    "              h=max(h,books[j][1])\n",
    "              r-=books[j][0]\n",
    "              if r<0:\n",
    "                  break\n",
    "              res=min(res,g(j+1)+h)\n",
    "           return res\n",
    "        return g(0)      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int) -> int:\n",
    "            if i < 0: return 0  # 没有书了，高度是 0\n",
    "            res, max_h, left_w = inf, 0, shelf_width\n",
    "            for j in range(i, -1, -1):\n",
    "                left_w -= books[j][0]\n",
    "                if left_w < 0: break  # 空间不足，无法放书\n",
    "                max_h = max(max_h, books[j][1])  # 从 j 到 i 的最大高度\n",
    "                res = min(res, dfs(j - 1) + max_h)\n",
    "            return res\n",
    "        return dfs(len(books) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:\n",
    "        n = len(books)\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == n: return 0  # 没有书了，高度是 0\n",
    "            res, max_h, left_w = inf, 0, shelf_width\n",
    "            for j in range(i, n):\n",
    "                left_w -= books[j][0]\n",
    "                if left_w < 0: break\n",
    "                max_h = max(max_h, books[j][1])  # 从 j 到 i 的最大高度\n",
    "                res = min(res, dfs(j + 1) + max_h)\n",
    "            return res\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i:int)->int:\n",
    "            if i<0:\n",
    "                return 0\n",
    "            res,max_h,left_w=inf,0,shelf_width\n",
    "            for j in range(i,-1,-1):\n",
    "                left_w-=books[j][0]\n",
    "                if left_w<0:\n",
    "                    break\n",
    "                max_h=max(max_h,books[j][1])\n",
    "                res=min(res,dfs(j-1)+max_h)\n",
    "            return res\n",
    "        return dfs(len(books)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "\n",
    "        n = len(books)\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i:int)->int:\n",
    "            if i<0:\n",
    "                return 0\n",
    "            lw = shelfWidth\n",
    "            maxh = 0\n",
    "            res = inf\n",
    "            for j in range(i,-1,-1):\n",
    "                lw -= books[j][0]\n",
    "                if lw < 0 :\n",
    "                    break\n",
    "                maxh = max(maxh,books[j][1])\n",
    "                res  = min(dfs(j-1)+maxh,res)\n",
    "            return res \n",
    "        return dfs(n-1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dp(input):\n",
    "            width = 0\n",
    "            high = 0\n",
    "            out = inf\n",
    "            if input == len(books): \n",
    "                print(\"good\")\n",
    "                return 0\n",
    "                \n",
    "            for i in range(input, len(books)):\n",
    "                width += books[i][0]\n",
    "                if width  > shelfWidth: break\n",
    "                high = max(high, books[i][1])\n",
    "                out = min(out, high+dp(i+1))\n",
    "\n",
    "\n",
    "            return out\n",
    "\n",
    "        return dp(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        n=len(books)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i<0: \n",
    "                return 0\n",
    "            total=books[i][0]\n",
    "            mx=books[i][1]\n",
    "            res=dfs(i-1)+mx\n",
    "            for j in range(i-1,-1,-1):\n",
    "                total+=books[j][0]\n",
    "                if total>shelfWidth:\n",
    "                    break\n",
    "                mx=max(mx,books[j][1])\n",
    "                res=min(dfs(j-1)+mx,res)\n",
    "            return res\n",
    "        return dfs(n-1)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        # 书架整体的高度为各层高之和。摆放书的顺序与给定图书数组 books 顺序相同。它们的厚度之和小于等于书架的宽度 shelfWidth\n",
    "        n = len(books)\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = math.inf\n",
    "            tmpwith = 0\n",
    "            mx = 0\n",
    "            for j in range(i,n):\n",
    "                mx = max(mx,books[j][1]) #计算当前高度\n",
    "                if tmpwith+books[j][0] <= shelfWidth: \n",
    "                    tmpwith += books[j][0]\n",
    "                    res = min(res,mx+dfs(j+1))\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            return res\n",
    "        res = dfs(0)\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i<0:\n",
    "                return 0\n",
    "            res, max_h, left_w = inf, 0, shelfWidth\n",
    "            for j in range(i,-1,-1):\n",
    "                left_w -= books[j][0]\n",
    "                if left_w<0: break\n",
    "                max_h = max(max_h, books[j][1])\n",
    "                res = min(res, dfs(j-1) + max_h)\n",
    "            return res\n",
    "\n",
    "        return dfs(len(books)-1)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
